package 剑指offer;

import java.util.Stack;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

public class 对称二叉树 {
    /*
	 * 	         	8
	 * 	      6	            6
	 *   5 	    7      7       5
	 5    7   7   5  5   7    7  5

    */


    //使用讨论中的代码
    static boolean isSymmetricalDFS(TreeNode pRoot) {
        if (pRoot == null) return true;
        Stack<TreeNode> s = new Stack<>();
        s.push(pRoot.left);
        s.push(pRoot.right);
        while (!s.empty()) {
            TreeNode right = s.pop();//成对取出
            TreeNode left = s.pop();
            if (left == null && right == null) continue;
            if (left == null || right == null) return false;
            if (left.val != right.val) return false;
            //成对插入
            s.push(left.left);
            s.push(right.right);
            s.push(left.right);
            s.push(right.left);
        }
        return true;

    }

    /*
    * 	         	8
    * 	      6	            6
    *   5 	    7      7       5
    5    6   7   5  5   7    6  5

   */
    static boolean isSymmetricalDFSMy(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left != null && right != null&&left.val==right.val) {
            return isSymmetricalDFSMy(left.left, right.right) &&
                    isSymmetricalDFSMy(left.right, right.left);

        }
        return false;
    }
    static boolean isSymmetrical(TreeNode pRoot){
        if(pRoot==null){
            return  true;
        }
        return isSymmetricalDFSMy(pRoot.left, pRoot.right);
    }


    public static void printTree(TreeNode tree) {
        if (tree != null) {
            //System.out.print(tree.val+" ");//先序遍历
            printTree(tree.left);
            System.out.print(tree.val + " ");//MiddleMy
            printTree(tree.right);
            //System.out.print(tree.val+" ");//后序遍历
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(6);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(7);
        root.right.left = new TreeNode(9);
        root.right.right = new TreeNode(11);
        printTree(root);
        System.out.println("\n" + isSymmetrical(root));
        printTree(root);


    }

}
